#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <filesystem>
#include <iostream>     // std::cout
#include <algorithm>    // std::shuffle
#include <array>        // std::array
#include <random>       // std::default_random_engine
#include <chrono>       // std::chrono::system_clock

void print_array(const std::vector<int>& vec)
{
	int enter_number = 0;
	for (auto node : vec)
	{
		std::cout << node << " ";
		if (++enter_number >= 5)
		{
			enter_number = 0;
			std::cout << "\n";
		}
	}

}

void qsort(std::vector<int>& vec, std::size_t left, std::size_t right)
{
	if (left >= right)
	{
		return;
	}

	int i = left;
	int j = right;
	int key = vec[i];

	while (i < j)
	{
		while (i <j && key <=vec[j])
		{
			j--;
		}
		vec[i] = vec[j];
		while (i < j && key >= vec[i])
		{
			i++;
		}
		vec[j] = vec[i];
	}
	vec[i] = key;
	qsort(vec, left, i - 1);
	qsort(vec, i+1, right);
}

void qsort_manual(int a[], int left, int right)
{
	if (left > right)
	{
		return;
	}
	int i = left;
	int j = right;
	int key = a[i];
	while (i < j)
	{
		while (i < j && key <= a[j])
		{
			j--;
		}
		a[i] = a[j];
		while (i < j && key >= a[i])
		{
			i++;
		}
		a[j] = a[i];
	}
	a[i] = key;
	qsort_manual(a, left, i - 1);
	qsort_manual(a, i + 1, right);
}


int main(int argn,char *argc[]) {
	std::vector<int> vec;
	for (size_t i = 0; i < 10; i++)
	{
		vec.emplace_back(i);
	}
	print_array(vec);

	std::random_device rd;
	std::mt19937 g(rd());
	std::shuffle(vec.begin(), vec.end(), g);
	std::cout << "\n--------------------\n";
	print_array(vec);

	std::cout << "\n--------------------\n";
	qsort(vec, 0, vec.size() - 1);
	print_array(vec);

    return 0;
}
